package 动态规划;

public class 不同路径Ⅱ {
    class Solution{
        //obstacleGrid为阻碍物的位置 其实很多和不同路径Ⅰ差不多 只不过是限制条件不同
        public int uniquePathsWithObstacles(int[][] obstacleGrid){
          int n = obstacleGrid.length; int m = obstacleGrid[0].length;
          int[][] dp = new int[n][m];
          //初始化
            for (int i = 0; i < m; i++) {
                //有障碍就结束循环 后面的不用算了 因为这一个方向有障碍就后面都不通的
                if (obstacleGrid[0][i] == 1) break;
               dp[0][i] = 1;
            }
            for (int i = 0; i < n; i++) {
                if (obstacleGrid[i][0] == 1) break;
                dp[i][0] = 1;
            }
            for (int i = 0; i < n ; i++) {
                for (int j = 0; j < m; j++) {
                    //如果有障碍就跳出当前循环 进入下一个循环 认为这条路不通了
                    if (obstacleGrid[i][j] == 1) continue;
                    dp[i][j] = dp[i-1][j]+dp[i][j-1];
                }
            }

            return dp[n-1][m-1];
        }
    }
}
